package com.Dec_Ten;

import java.util.ArrayList;
import java.util.List;

/**
 * 864. 获取所有钥匙的最短路径
 * 给定一个二维网格 grid ，其中：
 *
 * '.' 代表一个空房间
 * '#' 代表一堵
 * '@' 是起点
 * 小写字母代表钥匙
 * 大写字母代表锁
 * 我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
 *
 * 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
 *
 * 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/11/10 19:50
 */

public class Solution864 {

    static int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};

    public int shortestPathAllKeys(String[] grid) {
        int n=grid.length,m=grid[0].length();
        int keyNum=0;
        List<int[]> list=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c=grid[i].charAt(j);
                if (c=='@') {
                    list.add(new int[]{i,j,0});
                }
                if (c>='a'&&c<='z'){
                    keyNum++;
                }
            }
        }
        //在每一个区域收集到（不同数目不同类别）的钥匙所需要的步长
        int[][][] dist=new int[n][m][1<<keyNum];
        //BFS
        while (!list.isEmpty()) {
            int[] arr=list.remove(0);
            int x=arr[0];
            int y=arr[1];
            int s=arr[2];
            int step=dist[x][y][s];
            for (int[] dir:dirs){
                int xx=x+dir[0];
                int yy=y+dir[1];
                int ss=s;
                if (xx<0||xx>=n||yy<0||yy>=m){
                    continue;
                }
                char c=grid[xx].charAt(yy);
                if (c=='#')
                {
                    continue;
                }
                if (c>='A'&&c<='Z')
                {
                    if ((s>>(c-'A')&1)!=1)
                    {
                        continue;
                    }
                }
                if ('a' <= c && c <= 'z') { // 遇到钥匙
                    ss |= 1 << (c - 'a'); // 把钥匙捡起来放入物品箱
                }
                if (ss == (1 << keyNum) - 1) {
                    return step + 1; // 每把钥匙都收集到了
                }
                if (dist[xx][yy][ss]==0||step+1<dist[xx][yy][ss])
                {
                    dist[xx][yy][ss]=step+1; //更新最小步数;
                    list.add(new int[]{xx,yy,ss});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution864 solution864=new Solution864();
        System.out.println(solution864.shortestPathAllKeys(new String[]{"@..aA","..B#.","....b"}));
    }
}
